# !/usr/bin/env python
# -*- coding: utf-8 -*-
"""
@Time        : 2021/"v4"/17 15:23
@Author      : Albert Darren
@Contact     : 2563491540@qq.com
@File        : find_shortest_path.py
@Version     : Version 1.0.0
@Description : TODO
@Created By  : PyCharm
"""


def dijkstra(graph, source, inf=float('inf')):
    """
    使用 Dijkstra 算法计算指定点 v0 到图 G 中任意点的最短路径的距离,此方法不能解决负权值边的图
    :param graph: 图
    :param source: 源结点
    :param inf: 设定的无限远距离值
    :return:源点到所有点(包括本身)的最短距离和路线
    """
    book = set()
    # 源顶点到其余各顶点的初始路程
    distance = dict((k, inf) for k in graph.keys())
    distance[source] = 0
    shortest_path = []
    while len(book) < len(graph):
        book.add(source)  # 确定当前顶点的距离
        for w in graph[source]:  # 以当前点的中心向外扩散
            if distance[source] + graph[source][w] < distance[w]:  # 如果从当前点扩展到某一点的距离小于已知最短距离
                distance[w] = distance[source] + graph[source][w]  # 对已知距离进行更新
                shortest_path.append((source, w))
                # if source in shortest_path:
                #     shortest_path[source].append(w)
                # else:
                #     shortest_path[source] = [w]
        new = inf  # 从剩下的未确定点中选择最小距离点作为新的扩散点
        for v in distance.keys():
            if v in book:
                continue
            if distance[v] < new:
                new = distance[v]
                source = v
    return distance, shortest_path


def get_shortest_path(source, target, shortest_path):
    """
    获得最短路线
    :param source: 源结点
    :param target: 目标结点
    :param shortest_path: 最短路径
    :return: 最短路线
    """
    path = []
    for first, second in shortest_path:
        if first == source:
            path.append(second)
            source = second
        if second == target:
            path.append(second)
            return path


if __name__ == '__main__':
    # Dijkstra算法——通过边实现松弛
    # 指定一个点到其他各顶点的路径——单源最短路径
    # 初始化图参数
    dict_graph = {"v1": {"v1": 0, "v2": 5},
                  "v2": {"v1": 5, "v2": 0, "v3": 50, "v6": 10},
                  "v3": {"v2": 50, "v3": 0, "v4": 20, "v5": 10},
                  "v4": {"v3": 20, "v4": 0, "v5": 60, "v6": 30},
                  "v5": {"v3": 10, "v4": 60, "v5": 0, "v6": 100},
                  "v6": {"v2": 10, "v4": 30, "v5": 100, "v6": 0}}

    # 每次找到离源点最近的一个顶点，然后以该顶点为重心进行扩展
    # 返回源点到所有点(包括本身)的最短路径
    dis, way = dijkstra(dict_graph, source="v1")
    print("v1到v5结点的最短距离是:{}".format(dis["v5"]))  # {'v1': 0, 'v2': 5, 'v3': 55, 'v4': 45, 'v5': 65, 'v6': 15}
    print("v1到v5结点的最短路线是:{}".format(get_shortest_path("v1", "v5", way)))

